from typing import List
from util import draw_graph

# 邻接表建 有向图
def build_digraph_adjacency_matrix2(num_vertices, edges) -> List[List[int]]:
    graph = [[] for _ in range(num_vertices)]
    for u, v in edges:
        graph[u].append(v)
    return graph

# dfn 先序编号，原始节点 -> dfn编号
def dfn(num_vertices, graph: List[List[int]], root: int) -> List[int]:
    dfn = [0] * num_vertices
    id = 1
    def f(u):
        nonlocal id, dfn
        dfn[u] = id     # 先序，从小到大的dfn编号
        id += 1
        for v in graph[u]:
            f(v)
    f(root)
    return dfn
def size(num_vertices, graph: List[List[int]], root: int) -> List[int]:
    size = [0] * num_vertices
    def f(u):
        s = 1
        for v in graph[u]:
            s += f(v)
        size[u] = s     # 后续，统计大下
        return s
    f(root)
    return size


# 二叉树的
# sizes = [0] * num_vertices
# deeps = [0] * num_vertices
# # g函数：填充dfn编号，和统计sizes以dfn编号为下标
# def g(root, id):
#     if not root: return
#     dfn[root.val] = id  # 先序统计dfn编号
#     l_size = g(root.left, id + 1)
#     r_size = g(root.right, id + l_size + 1)
#     size = 1 + l_size + r_size
#     sizes[id] = size  # 后续统计size，以dfn编号为下标
#     return size

# 树结构的
# def f(u, id):
#     dfn[u], sizes[id], xor_sums[id] = id, 1, nums[u]
#     for v in graph[u]:
#         if dfn[v] != -1: continue
#         f(v, id + sizes[id])
#         sizes[id] += sizes[dfn[v]]
#         xor_sums[id] ^= xor_sums[dfn[v]]

# test
if __name__ == '__main__':
    num_vertices = 7
    edges = [
        [3,4],[3,5], [4,1],[5,6],[5,0],[6,2]
    ]
    graph = build_digraph_adjacency_matrix2(num_vertices, edges)
    draw_graph(num_vertices, edges)
    dfn_arr = dfn(num_vertices, graph, 3)
    size_arr = size(num_vertices, graph, 3)
    print(dfn_arr, size_arr, sep='\n')
